链表

链表是引用的加强应用.
知识点前提：依赖于引用传递；this表示当前对象。

链表基本概念

1.链表是一种简单的数据结构，功能是依靠引用关系实现多个数据的保存。

根据上图编写代码：

要求：定义一个Node类，保存String类型数据，同时拥有下一个节点的引用。

// 每个链表由多个节点组成
class Node { // 定义节点类
    private String data; // 要保存的数据
    private Node next;   // 要保存的下一个节点

    // 每个Node对象都必须保存相应的数据
    public Node(String data) { // 有数据才有Node
        this.data = data;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node getNext() {
        return this.next;
    }

    public String getData() {
        return this.data;
    }
}

Node类专门负责保存节点关系，需要其他类负责Node之间的关系匹配。
范例：使用循环取出数据

public class Demo {
    public static void main(String[] args) {
        // 1. 设置数据
        Node root = new Node("火车头");
        Node n1 = new Node("车厢A");
        Node n2 = new Node("车厢B");
        root.setNext(n1);
        n1.setNext(n2);
        // 2. 取出数据
        Node currentNode = root; //从根节点开始读取数据
        while (currentNode != null) { // 当前节点存在数据
            System.out.println(currentNode.getData());
            // 将下一节点设置为当前节点
            currentNode = currentNode.getNext();
        }
    }
}

利用循环取出数据不够便捷，应使用递归。
范例：使用递归取出数据

public class Demo {
    public static void main(String[] args) {
        // 1. 设置数据
        Node root = new Node("火车头");
        Node n1 = new Node("车厢A");
        Node n2 = new Node("车厢B");
        root.setNext(n1);
        n1.setNext(n2);
        print(root);
    }
    public static void print(Node current){
        if (current == null){ // 节点不存在
            return ; // 结束方法调用
        }
        System.out.println(current.getData());
        print(current.getNext()); // 递归调用
    }
}

因为循环次数未知，所以使用while循环。节点操作中，递归比while循环更直观。

问题：为什么要设置Node类
答：数据本身不具有先后关系，因此需要使用Node类封装份数据，同时利用Node类指向下一节点。

链表基本实现

通过分析发现：

(1)用户操作过程中，Node类应该是不可见的，即用户无需关注Node类的结构
(2)Node之间的关系不应该由用户定义，而应该由一个专门的类处理。

范例：定义Link类，隐藏Node类
程序要描述的步骤如下：
第一步：

第二步：

第三步：

第四步：

// 处理Node对象间关系
class Link {
    private Node root; // 根节点

    // 设置数据
    public void add(String data) {
        // 为了设置数据的先后关系，将data包装在Node对象中
        Node newNode = new Node(data);
        if (this.root == null) { // 保存数据时，根节点不存在
            // 该判断执行一次，因为链表只有一个根节点
            this.root = newNode; // 将新节点设置为根节点
        } else { // 根节点存在
            // 新节点应交给Node决定
            // 从root之后设置合适的位置
            this.root.addNode(newNode);
        }
    }

    // 输出数据
    public void print() {
        if (this.root != null) {
            this.root.printNode();
        }
    }
}

范例:根据Link类，修改Node类

class Node { 
    private String data; 
    private Node next;  

    public Node(String data) { 
        this.data = data;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node getNext() {
        return this.next;
    }

    public String getData() {
        return this.data;
    }

    // 添加节点
    // 第一次Link调用: this = link.root
    // 第二次Node调用：this = link.root.next
    // 第三次Node调用：this = link.root.next.next
    public void addNode(Node newNode) {
        if (this.next == null) { // 当前节点的next为空
            this.next = newNode; // 保存为新节点
        } else { 
            // 当前节点的next的next继续保存
            this.next.addNode(newNode);
        }
    }
    // 第一次Link调用: this = link.root
    // 第二次Node调用：this = link.root.next
    // 第三次Node调用：this = link.root.next.next
    public void printNode() {
        System.out.println(this.data); // 输出当前节点数据
        if (this.next != null) { // 当前节点有next
            this.next.printNode(); // 输出next节点信息
        }
    }
}

范例：测试

public class Demo {
    public static void main(String[] args) {
        Link link = new Link(); // 负责数据操作
        // 增加数据
        link.add("火车头");
        link.add("车厢A");
        link.add("车厢B");
        // 输出数据
        link.print();
    }
}

由上述代码可知链表操作的基本特点：

（1）对于客户端而言Node是不可见的，只能利用Link中的方法
（2）Link类的功能是控制Node对象的产生和根节点的使用；
（3）Node类的功能是保存数据以及配置引用关系。

可用链表基本结构

1.可用链表指的是能实现数据的增删改查的链表。
2.可用链表开发要求：Node类负责节点数据的保存以及节点关系的匹配，因此Node类不能被单独使用，即外部不能绕过Link去使用Node
范例：修改Node结构，使得Node类只能被Link类使用

思路：将Node类变为private定义的内部类。

class Link { // 链表类，外部可见
    // Node定义在内部让其只为Link服务
    private class Node { 
        private String data; // 保存数据
        private Node next; // 引用关系

        public Node(String data) { 
            this.data = data;
        }
    }

    // ====================以上为内部类=====================
    private Node root; // 根节点
}

上述代码即为可用链表的基本结构，后续为其增加功能代码。

增加数据功能

思路：数据的增加应由Link负责节点对象的产生，以及根节点的维护。节点间的关系匹配，由Node类处理。

范例：Node类中添加addNode()，Link类中添加add()

// 设置关系
public void addNode(Node newNode) {
    if (this.next == null) {
        this.next = newNode;
    } else {
        this.next.addNode(newNode);
    }
}

public void add(String data) {
    if (data == null) { // 输入数据为空
        return;
    }
    Node newNode = new Node(data); // 要保存的数据
    if (this.root == null) { // 根节点不存在
        this.root = newNode; // 设为根节点
    } else { //  根节点存在，交由Node处理
        this.root.addNode(newNode);
    }
}

范例：测试

public class Demo {
    public static void main(String[] args) {
        Link link = new Link();
        link.add("火车头");
        link.add("车厢A");
        link.add("车厢B");
    }
}

获取链表长度

思路：每个链表对象都只有一个root，可以在Link类中设置count属性，随后每次添加数据后，count自增。

范例：修改Link类
（1）增加count属性:private int count = 0; // 节点的个数
（2）在add()添加统计节点个数的操作

public void add(String data) {
   if (data == null) { 
       return;
   }
   Node newNode = new Node(data); 
   if (this.root == null) { 
       this.root = newNode; 
   } else { // 
       this.root.addNode(newNode);
   }
   this.count++; // 每次增加节点，count+1
}

（3）添加获取链表长度的方法size()

public int size() {
    return this.count;
}

（4）判断链表是否为空，有两种方式，一是判断root是否为null，二是判断count是否为0，在此采用第二种方式，在Link类中添加isEmpty()

public boolean isEmpty() {
    return this.count == 0;
}

内容查询

思路：判断链表中是否存在某数据，以String为例，仅需遍历链表中的数据，与要查询的数据记性匹配（使用equals(String str)），如果匹配成功返回true，反之返回false。

根据上图编写代码：
（1）Link中添加contains()

public boolean contains(String data) {
    if (data == null || root == null) {
        return false;
    }
    return this.root.containsNode(data);
}

Link从root节点开始查询数据是否存在，数据不存在，Node开始查询非根节点。
（2）Node中添加containsNode()

public boolean containsNode(String data) {
    if (data.equals(this.data)) { // 当前数据等于要目标数据
        return true; // 结束查询
    } else { // 当前数据不等于目标数据
        if (this.next != null) { // 有后续节点
            return this.next.containsNode(data);
        } else { 
            return false;
        }
    }
}

（3）测试

public class Demo {
    public static void main(String[] args) {
        Link link = new Link();
        link.add("火车头");
        link.add("车厢A");
        link.add("车厢B");
        System.out.println(link.contains("火车头"));
    }
}

案例中使用的是String类型数据，所以判断数据使用equals(String str)。如果判断的是自定义类型数据，就需要定义一个对象比较的方法，方法名暂定为compare()。

根据索引取得数据

链表中保存有多个对象。数组也可以保存多个对象。链表和数组相比优势在于没有长度限制。因此链表相当于一个动态对象数组，具备像数组那样根据索引取得元素的功能。
由于是动态对象数组，所以元素的索引也是动态生成的。

根据上图，编写代码：
（1）Link中增加foot属性，表示Node的索引:private int foot = 0; // 索引
每次查询前，应该重置为0.链表查询数据前应先判断要查询的索引小于索引总数。

public String get(int index) {
    if (index > this.count) { // 超出查询范围
        return null;
    }
    this.foot = 0;
    return this.root.getNode(index); // 查询交给Node类
}

（2）Node定义getNode()，内部类和外部类间可以方便地进行私有属性的访问。

public String getNode(int index) {
    // 当前foot内容与要查询的索引比较
    // foot自增，目的是下次查询方便
    if (Link.this.foot++ == index) {
        return this.data;
    } else {
        return this.next.getNode(index);
    }
}

修改链表数据

修改和查询思路差不多，不同的是查询是当满足索引值时，返回数据；修改是满足索引时，对数据重新赋值。

（1）Link添加set(int index, String data)

public void set(int index, String data) {
    if (index > this.count) {
        return;
    }
    this.foot = 0; // 重置foot,作为索引
    this.root.setNode(index, data); // Node进行修改数据
}

（2）Node添加setNode(int index, String data)

public void setNode(int index, String data) {
    if (Link.this.foot++ == index) {
        this.data = data;
    } else {
        this.next.setNode(index, data);
    }
}

删除链表数据

删除链表数据应分为两种情况：
（1）要删除的是根节点，root.next()变为root，在Link中处理，因为由Link来维护root；
（2）要删除的是非根节点，当前节点的上一节点.next()=当前节点.next()，即空出了当前节点。非根节点应交由Node处理。

1.Node添加removeNode(Node previous, String data)

public void removeNode(Node previous, String data) {
    // 参数中传递上一个节点和要删除的数据
    if (data.equals(this.data)) {
        previous.next = this.next;
    } else {
        this.next.removeNode(this, data);
    }
}

2. Link添加remove(String data)

public void remove(String data) {
    if (this.contains(data)) { // 判断数据是否存在
        if (data.equals(this.root.data)) { // 判断数据是否是root数据
            this.root = this.root.next;
        } else {
            // root是Node对象，此处直接访问内部类私有操作
            this.root.next.removeNode(this.root, data);
        }
this.count -- ; // 删除后数据个数减少
    }
}

对象数组转换

开发中，类中不应该有输出语句。想输出数据应将数据返回到调用处。链表属于动态数组，因此可以将链表以对象数组的形式返回。

由上图可知，Link的toArray()要返回一个对象数组，且该数组也要由Node操作。因此该数组应定义为Link的属性。
（1）Link添加一个数组属性，便于Node和Link访问。添加toArray()

private String[] retArray; // 返回的数组

public String[] toArray() {
    if (this.root == null) {
        return null;
    }
    this.foot = 0; // 需要脚标控制
    this.retArray = new String[this.count]; // 根据保存内容开辟数组
    this.root.toArrayNode();
    return this.retArray;
}

（2）Node添加toArrayNode()进行数组数据保存

public void toArrayNode() {
    Link.this.retArray[Link.this.foot++] = this.data;
    if (this.next != null) {
        this.next.toArrayNode();
    }
}

链表数据变为对象数组取出是重要功能！

链表使用

上述链表只能操作String数据。下面要使用链表操作自定义类，由于链表具有contains()，因此类中需定义对象比较的方法。

（1）定义Book类（setter/getter暂时省略）

class Book {
    private String title;
    private double price;

    public Book(String title, double price) {
        this.title = title;
        this.price = price;
    }

    public String getInfo() {
        return "书名：" + this.title + ",价格" + this.price;
    }

    public boolean compare(Book book) {
        if (book == null) {
            return false;
        }
        if (this == book) {
            return true;
        }
        if (this.title.equals(book.title)
                && this.price == book.price) {
            return true;
        } else {
            return false;
        }
    }
}

（2）修改链表

class Link { 
    private class Node { // 节点类
        private Book data; // 保存数据
        private Node next; // 引用关系

        public Node(Book data) { 
            this.data = data;
        }

        // 设置关系
        public void addNode(Node newNode) {
            if (this.next == null) {
                this.next = newNode;
            } else {
                this.next.addNode(newNode);
            }
        }

        // 数据查询
        public boolean containsNode(Book data) {
            if (data.equals(this.data)) { // 当前数据等于要目标数据
                return true; // 结束查询
            } else { // 当前数据不等于目标数据
                if (this.next != null) { // 有后续节点
                    return this.next.containsNode(data);
                } else { // 没有后续节点
                    return false;
                }
            }
        }


        public Book getNode(int index) {
            // 当前foot内容与要查询的索引比较
            // foot自增，目的是下次查询方便
            if (Link.this.foot++ == index) {
                return this.data;
            } else {
                return this.next.getNode(index);
            }
        }

        // 修改节点信息
        public void setNode(int index, Book data) {
            if (Link.this.foot++ == index) {
                this.data = data;
            } else {
                this.next.setNode(index, data);
            }
        }

        // 删除非根节点
        public void removeNode(Node previous, Book data) {
            // 参数中传递上一个节点和要删除的数据
            if (data.equals(this.data)) {
                previous.next = this.next;
            } else {
                this.next.removeNode(this, data);
            }
        }

        public void toArrayNode() {
            Link.this.retArray[Link.this.foot++] = this.data;
            if (this.next != null) {
                this.next.toArrayNode();
            }
        }
    }


    // ====================以上为内部类=====================
    private Node root; // 根节点
    private int count = 0; // 节点的个数
    private int foot = 0; // 索引
    private Book[] retArray; // 返回的数组

    public void add(Book data) {
        if (data == null) { // 输入数据为空
            return;
        }
        Node newNode = new Node(data); // 要保存的数据
        if (this.root == null) { // 根节点不存在
            this.root = newNode; // 设为根节点
        } else { //  根节点存在，交由Node处理
            this.root.addNode(newNode);
        }
        this.count++; // 每次增加节点，count+1
    }

    // 获取链表长度
    public int size() {
        return this.count;
    }

    // 判断是否为空链表
    public boolean isEmpty() {
        return this.count == 0;
    }


    // 判断数据是否存在
    public boolean contains(Book data) {
        if (data == null || root == null) {
            return false;
        }
        return this.root.containsNode(data);
    }

    // 根据索引获取信息
    public Book get(int index) {
        if (index > this.count) { // 超出查询范围
            return null;
        }
        this.foot = 0;
        return this.root.getNode(index); // 查询交给Node类
    }

    // 设置信息
    public void set(int index, Book data) {
        if (index > this.count) {
            return;
        }
        this.foot = 0; // 重置foot,作为索引
        this.root.setNode(index, data); // Node进行修改数据
    }


    // 判断删除节点是否为root
    public void remove(Book data) {
        if (this.contains(data)) { // 判断数据是否存在
            if (data.equals(this.root.data)) { // 判断数据是否是root数据
                this.root = this.root.next;
            } else {
                // root是Node对象，此处直接访问内部类私有操作
                this.root.next.removeNode(this.root, data);
            }
            this.count--; // 删除后数据个数减少
        }
    }

    public Book[] toArray() {
        if (this.root == null) {
            return null;
        }
        this.foot = 0; // 需要脚标控制
        this.retArray = new Book[this.count]; // 根据保存内容开辟数组
        this.root.toArrayNode();
        return this.retArray;
    }
}

（3）测试

public class Demo {
    public static void main(String[] args) {
        Link all = new Link();
        all.add(new Book("Java开发", 69.8));
        all.add(new Book("JSP", 78.8));
        all.add(new Book("C++开发", 19.8));
        System.out.println("保存书的个数：" + all.size());
        System.out.println(all.contains(new Book("Java开发", 69.8)));
        all.remove(new Book("C++开发", 19.8));
        Book[] books = all.toArray();
        for (int x = 0; x < books.length; x++) {
            System.out.println(books[x].getInfo());
        }
    }
}

链表的最佳应用就是横向替换对象数组。

在映射中使用链表

链表属于动态对象数组。之前进行数据表映射时，都会出现对象数组的概念，现在就用链表来进行对象保存。本节以一对多为例，即用前文中的省份-城市表为例：

（1）对于使用链表的类，要添加对象比较的方法

class Province {
    private int pid;
    private String pname;
    private Link cities = new Link();

    public Link getCities() {
        return this.cities;
    }

    //getter/setter,无参构造方法略
    public Province(int pid, String pname) {
        this.pid = pid;
        this.pname = pname;
    }

    public boolean compare(Province province) {
        if (province == null) {
            return false;
        }
        if (this == province) {
            return true;
        }
        if (this.pid == province.pid && this.pname.equals(province.pname)) {
            return true;
        } else {
            return false;
        }
    }

    public String getInfo() {
        return "省份ID：" + this.pid + ",省份名称：" + this.pname;
    }
}


class City {
    private int cid;
    private String cname;
    private Province province;

    public void setProvince(Province province) {
        this.province = province;
    }

    public Province getProvince() {
        return this.province;
    }

    //getter/setter,无参构造方法略
    public City(int cid, String cname) {
        this.cid = cid;
        this.cname = cname;
    }

    public String getInfo() {
        return "城市ID：" + this.cid + ",城市名称：" + this.cname;
    }

    public boolean compare(City city) {
        if (city == null) {
            return false;
        }
        if (this == city) {
            return true;
        }
        if (this.cid == city.cid && this.cname.equals(city.cname)
                && this.province.compare(city.province)) {
            return true;
        } else {
            return false;
        }
    }
}

此时只需将链表中的Book改为City即可。
在此时发现问题：每定义一个新的类，链表就需要重新进行修改。方法解决了代码重复问题。但是该问题不属于代码重复，属于数据类型不同意，该问题需要依靠面向对象的特性的来结局。

总结

（1）本章所讲的只是最基础的单向链表；
（2）链表中应有如下方法：

This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接：http://yov.oschina.io/article/Java/Java Base/Java基础知识(十)/